# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: insert.py
@time: 2022/7/24 12:11
@author: LDC
"""
'''
3、插入排序
当前需要排序的元素(array[i])，跟已经排序好的最后一个元素比较(array[i-1])，
如果满足条件继续执行后面的程序，否则循环到下一个要排序的元素。
缓存当前要排序的元素的值，以便找到正确的位置进行插入。
排序的元素跟已经排序好的元素比较，比它大的向后移动(升序)。
要排序的元素，插入到正确的位置。
'''
import random
import time


def insertSort(list1):
    for i in range(1, len(list1)):
        if list1[i] < list1[i - 1]:  # 当前要排序的元素比前面的小
            index = i  # 保存当前元素的下标，这个变量是用来记录排序元素需要插入的位置
            temp = list1[i]  # 保存当前元素的值
            while index > 0 and list1[index - 1] > temp:  # 找到正确的排序位置
                list1[index] = list1[index - 1]  # 如果前面的比当前元素值大，就往后移动一位
                index -= 1
            if index != i:
                list1[index] = temp


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    insertSort(list1)
    end1 = time.perf_counter()
    print("插入排序      ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list1 == list4)
